Electronic transactions should be convenient, reliable, accurate and resistant to fraud. Certain electronic transactions should also protect the privacy of at least one party to the transaction. For example, a customer purchasing a service from a vendor over a network should be able to pay for the service in an electronic transaction without revealing their identity.
The need for one party to a transaction to remain private (e.g., anonymous) can conflict with the interests of another party to the transaction. For example, a vendor needs assurance that the an electronic transaction is reliable, e.g., that the customer in the transaction will pay for the services rendered by the vendor. Typically, a vendor uses information about a customer to assess the vendor's risk in engaging in the transaction, and to track down delinquent customers when necessary. A good electronic transaction system would accommodate both the privacy needs of one party and the reliability needs of another party.
Known electronic transaction systems generally fail to accommodate both privacy interests and reliability interests of different parties, typically sacrificing one in favor of the other. One known system, an anonymizer, protects the identity of a customer from being disclosed to a vendor, but the customer identity is known to the anonymizer, and a customer's activity can be profiled across vendors. See Community ConneXion, Inc. &lt;http://www.anonymizer.com&gt;. In a sense, the anonymizer is worse than a single vendor, because a single vendor can typically only profile a customer's behavior with respect to the vendor itself. On the other hand, the anonymizer can profile customer transactions across several vendors, not just one. The customer is thus forced to place considerable trust in the anonymizer, which if unwarranted, could lead to a substantial breach of the customer's privacy.
Another known system uses electronic cash ("e-cash"), wherein a customer obtains an electronic certificate that is redeemable at a vendor for the vendor's product. See D. Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, CACM 24, 2, Febuary 1981, pp. 84-88; D. Chaum, Security Without Identification: Transaction Systems to Make Big Brother Obsolete, CACM (28,10), October 1985, pp. 1030-1044; D. Chaum, A. Fiat, and M. Naor, Untraceable Electronic Cash, CRYPTO88, pp. 319-327; E. Brickell, P. Gemmell, and D. Kravitz, Trustee-based Tracing Extensions to Anonymous Cash and the Making of Anonymous Change, Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 457-466, San Francisco, Calif., 22-24 January 1995; M. Franklin and M. Yung, Towards Provably Secure Efficient Electronic Cash, Columbia University CS Technical Report, TR CUCS-018-92, 1992; and D. Simon, Anonymous Communication and Anonymous Cash, CRYPTO96, pp. 61-73. One known system uses credit card information to carry out an electronic transaction. Secure Electronic Transaction (SET) Specification, Aug. 1, 1996. As used herein, the term "product" includes a good and/or a service. Providing a service includes providing any kind of information. The electronic certificate is meant to be spent only once, and can be verified by the vendor before the vendor provides the product. One type of fraud to which these known systems can be vulnerable is the multiple spending of a certificate. Elaborate safeguards have been designed to detect when a certificate submitted for a product has already been spent. Many of these safeguards involve revealing the identity of the customer, thereby violating the customer's privacy.
A known technique for protecting the anonymity of a certificate owner is called blinding. See D. Chaum, Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms, CACM 24, 2, Febuary 1981, pp. 84-88; D. Chaum, Security Without Identification: Transaction Systems to Make Big Brother Obsolete, CACM (28,10), October 1985, pp. 1030-1044; and D. Chaum, A. Fiat, and M. Naor, Untraceable Electronic Cash, CRYPTO88, pp. 319-327. A customer chooses a nonce and a blinding factor. A nonce is a piece of data that, for practical purposes, is used only once. For example, a random number can be a nonce. Both the nonce and the blinding factor are known only to the customer. The customer applies the blinding factor to the nonce (e.g., by multiplying the nonce by the blinding factor), and submits the blinded nonce to a certification authority along with a payment. In exchange for the payment, the certification authority signs the blinded nonce to obtain a blinded certificate. The blinded certificate is returned to the customer. When the customer wishes to make a purchase, the customer unblinds the certificate (e.g., by dividing the certificate by the blinding factor) to obtain an unblinded certificate. Because only the customer knows the blinding factor, no other party can correlate the unblinded certificate with the blinded certificate. The customer submits the unblinded certificate along with the nonce to a vendor with a request for the desired product. The vendor can verify the validity of the unblinded certificate using the nonce upon which it is based using techniques known in the art. Because of the commutativity of modular arithmetic and the mathematical nature of the signing process, the signed nonce corresponds to the unblinded certificate. If the unblinded certificate is determined to be valid, then the vendor makes the product available to the customer. Otherwise, the product is not made available to the customer.
Although the use of blinding alone protects the anonymity of the customer, it is not sufficient to safeguard against certain types of fraud. For example, a customer can submit a blinded nonce to the certification authority along with $20, receive the blinded certificate, unblind it, and then submit the unblinded certificate as being worth $100. This is possible because the certification authority never really sees the actual certificate it is signing because of the blinding factor. Thus, although blinding alone protects privacy, it does not by itself provide adequate reliability.
The problem of reliably linking a denomination to a certificate is addressed by the use of hash functions. A hash is a one-way function whereby it is easy to obtain an output from a given input, but is very difficult to derive an input from a given output. To obtain a certificate that only a particular customer can use, the customer presents a certification authority (e.g., a bank) with a payment and a hashed nonce. The hash function used by the customer is also known by the bank. The bank signs the hashed nonce linked to a denomination to obtain a certificate, which is returned to the customer. To use the certificate, the customer redeems the certificate, the nonce and the denomination to a vendor, who in turn presents the certificate, the nonce and the denomination to the bank. The bank verifies the certificate using a publicly available verification key. If the certificate is verified as being valid, then the bank authorizes the vendor to provide the customer with the requested product, and credits the vendor's account. If the signature and the certificate do not correspond, then the bank notifies the vendor that the certificate is invalid. After the certificate is spent, the bank must record the hashed random number to prevent it from being spent again. The use of hash functions alone is reliable because in order to fraudulently spend a certificate, a third party would have to deduce the nonce from the certificate. This is made practically impossible by using a hash function to derive the certificate from the nonce. However, since the customer's certificate is known to the bank both during the initial certification process and the redemption process, the identity (and thus the privacy) of the customer can be compromised by the bank.
Balancing privacy and reliability interests across more than one transaction is challenging because a transaction which is reliable and private alone can often be correlated with other transactions from the same customer to compromise privacy, reliability, or both in known systems. Thus, a series of transactions could be unreliable and compromise privacy. As used herein, a series of transactions is meant to include both a single transaction, as well as more than one transaction. Privacy and reliability should be provided for both the case of a single transaction, and more than one related transaction.
An example of a series of transactions is a subscription service, e.g., paying a fee for a password that can be used to repeatedly access a service for a predetermined amount of time and/or use. A subscription service is one in which the customer pays an initial amount to receive a product from a vendor in installments. Note that in the degenerate case, a subscription service includes only a single transaction. In certain known electronic commerce systems, the customer makes an initial payment to a subscription vendor, who in return gives the customer means (such as a password) to periodically obtain the vendor's product over a predetermined period of time. Subscriptions are commonly sold on an individual basis. Under such a policy, for example, two individuals seeking a subscription should pay the vendor separately; each would then receive her own subscription and password. If one individual pays for a subscription and shares her password with a second person, then two people are able to receive the subscription vendor's product while only one is paying for it. This problem of sharing distinguishes an e-commerce system suitable for subscription services from known systems such as e-cash. In e-cash systems, a certificate is meant to be fungible and readily transferable. In an e-commerce system capable of supporting subscription services, such transferability must be prevented or curtailed.
To counter the sharing's threat to the reliability of a subscription transaction, the subscription vendor has a strong interest in monitoring the subscribing customer's behavior to ensure that the customer is not sharing her subscription with others who have not paid the vendor. For example, unusually high activity in a single account could indicate fraud, e.g., that many different individuals are making use of a single subscription. On the other hand, the customer may prefer to have her privacy respected and not to have her activity monitored. For example, a customer subscribing to a database service may wish to keep the searches she makes private. Likewise, a customer ordering pay-per-use movies may wish to keep the identity of the movies he orders confidential. These privacy interests should be accommodated by a good electronic transaction system in a subscription-type setting. Known techniques exist for issuing pseudonyms, thus linking customer behavior to the pseudonym rather than to the customer. However, these still allow profiles (e.g., of customer behavior) to be constructed if even one pseudonymous transaction is broken or accidentally identifies the customer. Then, all of the customer's past and future behavior can be linked to that customer. A better system for electronic transactions would not suffer from this limitation.
A good electronic transaction system would accommodate both the needs of the customer for privacy and of the vendor for reliability in a single electronic transaction, and in more than one related transaction, in part by preventing sharing.